In computation problems, often matrices are provided from a memory during data processing. One practical example is computation in polynomial remainder rings e.g. used for hashing, integrity check sums, message digests and random number generators. In a particular example, if the polynomial remainder rings are used as checksums they are called cyclic redundancy check (CRC) computations. In one implementation, in a CRC calculation core a vector-matrix multiplier is used to compute v mod p, where v is a polynomial and p is a generator polynomial of the CRC.
The mod-operation is computed by interpreting the coefficients for the polynomial v as a vector, and multiplying it with a matrix m(p) which only depends on p. In such computations involving matrices, it is desirable to compress the matrices for the purposes of accelerating the exchange of the matrix because less data has to be read from memory, and saving costs, because less memory capacity is needed per matrix. In relation to the cost saving aspect it will be appreciated that the saved costs have to be balanced against the associated costs of the decompressor.
The present invention seeks to provide a decompression method and system for decompressing matrices with piecewise redundant matrix rows.
US20050010630A1 relates to a method and an apparatus for determining a remainder in a polynomial ring. The apparatus for determining a remainder in a polynomial ring comprises a value buffer for storing a polynomial value, a factor memory for storing factors and a polynomial multiply unit connected to the factor memory for generating a polynomial product out of the factors and an input polynomial. The apparatus further comprises a matrix multiply unit connected to the polynomial multiply unit for generating a reduced product with reduced polynomial degree by multiplying the polynomial product with a reduction matrix. Finally the apparatus includes a multiplexer means for either conducting the reduced product or the polynomial value as the input polynomial to the polynomial multiply unit.